﻿// Accord Unit Tests
// The Accord.NET Framework
// http://accord-framework.net
//
// Copyright © César Souza, 2009-2017
// cesarsouza at gmail.com
//
//    This library is free software; you can redistribute it and/or
//    modify it under the terms of the GNU Lesser General Public
//    License as published by the Free Software Foundation; either
//    version 2.1 of the License, or (at your option) any later version.
//
//    This library is distributed in the hope that it will be useful,
//    but WITHOUT ANY WARRANTY; without even the implied warranty of
//    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
//    Lesser General Public License for more details.
//
//    You should have received a copy of the GNU Lesser General Public
//    License along with this library; if not, write to the Free Software
//    Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
//

namespace Accord.Tests.Math
{
    using System;
    using System.Collections.Generic;
    using Accord.Math;
    using Accord.Math.Optimization;
    using NUnit.Framework;
    using Munkres;

    [TestFixture]
    public class MunkresTest
    {

        [Test]
        public void minimize_test()
        {
            #region doc_example
            // This is the same example that is found in Wikipedia:
            // https://en.wikipedia.org/wiki/Hungarian_algorithm

            double[][] costMatrix =
            {
                //                      Clean bathroom, Sweep floors,  Wash windows
                /* Armond   */ new double[] {    2,           3,           3       },
                /* Francine */ new double[] {    3,           2,           3       },
                /* Herbert  */ new double[] {    3,           3,           2       },
            };

            // Create a new Hungarian algorithm
            Munkres m = new Munkres(costMatrix);

            bool success = m.Minimize();    // solve it (should return true)
            double[] solution = m.Solution; // Solution will be 0, 1, 2
            double minimumCost = m.Value;   // should be 6
            #endregion

            Assert.AreEqual(3, m.NumberOfTasks);
            Assert.AreEqual(3, m.NumberOfWorkers);

            Assert.IsTrue(success);
            Assert.AreEqual(6, minimumCost);
            Assert.AreEqual(0, solution[0]);
            Assert.AreEqual(1, solution[1]);
            Assert.AreEqual(2, solution[2]);
        }

        [Test]
        public void minimize_test2()
        {
            double[][] costMatrix = Jagged.Magic(5);

            var m = new Munkres(costMatrix);

            Assert.AreEqual(5, m.NumberOfTasks);
            Assert.AreEqual(5, m.NumberOfWorkers);

            bool success = m.Minimize();
            Assert.IsTrue(success);
            Assert.AreEqual(15, m.Value);
            Assert.AreEqual(2, m.Solution[0]);
            Assert.AreEqual(1, m.Solution[1]);
            Assert.AreEqual(0, m.Solution[2]);
            Assert.AreEqual(4, m.Solution[3]);
            Assert.AreEqual(3, m.Solution[4]);
        }

        [Test]
        public void minimize_test3()
        {
            // http://csclab.murraystate.edu/~bob.pilgrim/445/munkres.html

            double[][] costMatrix =
            {
                new double[] { 1, 2, 3 },
                new double[] { 2, 4, 6 },
                new double[] { 3, 6, 9 },
            };

            var m = new Munkres(costMatrix);

            Assert.AreEqual(3, m.NumberOfTasks);
            Assert.AreEqual(3, m.NumberOfWorkers);

            bool success = m.Minimize();
            Assert.IsTrue(success);
            Assert.AreEqual(10, m.Value);
            Assert.AreEqual(2, m.Solution[0]);
            Assert.AreEqual(1, m.Solution[1]);
            Assert.AreEqual(0, m.Solution[2]);
        }

        [Test]
        public void minimize_test_more_jobs()
        {
            double[][] costMatrix =
            {
                new double[] { 1, 2, 3, 4  },
                new double[] { 2, 4, 6, 8  },
                new double[] { 3, 6, 9, 12 },
            };

            var m = new Munkres(costMatrix);

            Assert.AreEqual(4, m.NumberOfTasks);
            Assert.AreEqual(3, m.NumberOfWorkers);

            bool success = m.Minimize();
            Assert.IsTrue(success);
            Assert.AreEqual(10, m.Value);
            Assert.AreEqual(2, m.Solution[0]);
            Assert.AreEqual(1, m.Solution[1]);
            Assert.AreEqual(0, m.Solution[2]);
        }

        [Test]
        public void minimize_test_more_jobs2()
        {
            // A = [ 1 2 3; 2 4 6; 3 6 9; 4 8 12 ]
            double[][] costMatrix =
            {
                new double[] { 1, 2,  3 },
                new double[] { 2, 4,  6 },
                new double[] { 3, 6,  9 },
                new double[] { 4, 8, 12 },
            };

            var m = new Munkres(costMatrix.Transpose());

            Assert.AreEqual(4, m.NumberOfTasks);
            Assert.AreEqual(3, m.NumberOfWorkers);

            bool success = m.Minimize();
            Assert.IsTrue(success);
            Assert.AreEqual(10, m.Value);
            Assert.IsTrue(m.starZ.IsEqual(new[] { 2, 1, 0, 3 }));
            Assert.IsTrue(m.Solution.IsEqual(new[] { 2, 1, 0 }));
        }

        [Test]
        public void minimize_test_more_workers()
        {
            // A = [ 1 2 3; 2 4 6; 3 6 9; 4 8 12 ]
            double[][] costMatrix =
            {
                new double[] { 1, 2,  3 },
                new double[] { 2, 4,  6 },
                new double[] { 3, 6,  9 },
                new double[] { 4, 8, 12 },
            };

            var m = new Munkres(costMatrix);

            Assert.AreEqual(3, m.NumberOfTasks);
            Assert.AreEqual(4, m.NumberOfWorkers);

            bool success = m.Minimize();

            Assert.AreEqual(3, m.validCol.Length);
            Assert.AreEqual(4, m.validRow.Length);

            Assert.IsTrue(success);
            Assert.AreEqual(10, m.Value);
            Assert.IsTrue(m.starZ.IsEqual(new[] { 2, 1, 0, 3 }));
            Assert.IsTrue(m.Solution.IsEqual(new[] { 2, 1, 0, Double.NaN }));
        }

        /*
        [Test, Ignore("This test was comparing against the old Munkres implementation.")]
        public void minimize_index_out_of_range1()
        {
            double[][] costMatrix = new double[][]
            {
                new double[] { 330, 456, 106, 120, 113, 84, 0, 20, 5 },
                new double[] { 246, 360, 62, 72, 69, 44, 8, 44, 9 },
                new double[] { 4.55555555555556, 33.8888888888889, 39.2222222222222, 36.5555555555556, 42.8888888888889, 56.5555555555556, 272.555555555556, 427.222222222222, 272.222222222222 },
                new double[] { 330, 456, 106, 120, 113, 84, 0, 20, 5 },
                new double[] { 246, 360, 62, 72, 69, 44, 8, 44, 9 },
                new double[] { 4.55555555555556, 33.8888888888889, 39.2222222222222, 36.5555555555556, 42.8888888888889, 56.5555555555556, 272.555555555556, 427.222222222222, 272.222222222222 },
                new double[] { 330, 456, 106, 120, 113, 84, 0, 20, 5 },
                new double[] { 246, 360, 62, 72, 69, 44, 8, 44, 9 },
                new double[] { 4.55555555555556, 33.8888888888889, 39.2222222222222, 36.5555555555556, 42.8888888888889, 56.5555555555556, 272.555555555556, 427.222222222222, 272.222222222222 }
            };

            MunkresProgram.Init(costMatrix.ToMatrix());

            var m = new Munkres(costMatrix);
            m.C = costMatrix.Copy();

            int step1 = m.RunStep(0);

            Assert.AreEqual(1, step1);

            bool done = false;
            while (step1 >= 0)
            {
                step1 = m.RunStep(step1);
                done = MunkresProgram.RunStep(done);

                Assert.IsTrue(step1 == MunkresProgram.step || (step1 == -1 && MunkresProgram.step == 7));
                Assert.IsTrue(m.C.IsEqual(MunkresProgram.C));
                for (int i = 0; i < m.M.Length; i++)
                    for (int j = 0; j < m.M[i].Length; j++)
                        Assert.AreEqual(m.M[i][j], MunkresProgram.M[i, j]);
            }

            Assert.AreEqual(9, m.NumberOfTasks);
            Assert.AreEqual(9, m.NumberOfWorkers);

            bool success = m.Minimize();
            Assert.IsTrue(success);
            Assert.AreEqual(275, m.Value, 1e-10);
            Assert.AreEqual(8, m.Solution[0]);
            Assert.AreEqual(5, m.Solution[1]);
            Assert.AreEqual(7, m.Solution[2]);
            Assert.AreEqual(2, m.Solution[3]);
            Assert.AreEqual(1, m.Solution[4]);
            Assert.AreEqual(4, m.Solution[5]);
            Assert.AreEqual(6, m.Solution[6]);
            Assert.AreEqual(3, m.Solution[7]);
            Assert.AreEqual(0, m.Solution[8]);
        }
        */

        [Test]
        public void minimize_rectangular_inf()
        {
            double inf = Double.PositiveInfinity;

            double[][] costMatrix =
            {
                new double[] { 1.0, inf, inf },
                new double[] { 3.0, inf, inf },
                new double[] { 1.0, 5.0, 0.5 },
            };

            var m = new Munkres(costMatrix);

            Assert.AreEqual(3, m.NumberOfTasks);
            Assert.AreEqual(3, m.NumberOfWorkers);

            bool success = m.Minimize();
            Assert.IsTrue(success);
            Assert.AreEqual(1.5, m.Value);
            Assert.IsTrue(m.starZ.IsEqual(new[] { 0, 1, 2 }));
            Assert.IsTrue(m.Solution.IsEqual(new[] { 0, Double.NaN, 2 }));
        }

        public void minimize_invalid_row()
        {
            double inf = Double.PositiveInfinity;

            double[][] costMatrix =
            {
                new double[] { 1.0, inf, inf, inf },
                new double[] { 3.0, inf, inf, inf },
                new double[] { 1.0, inf, 5.0, 0.5 },
            };

            var m = new Munkres(costMatrix);

            Assert.AreEqual(3, m.NumberOfTasks);
            Assert.AreEqual(3, m.NumberOfWorkers);

            bool success = m.Minimize();
            Assert.IsTrue(success);
            Assert.AreEqual(1.5, m.Value);
            Assert.IsTrue(m.starZ.IsEqual(new[] { 0, 1, 2 }));
            Assert.IsTrue(m.Solution.IsEqual(new[] { 0, Double.NaN, 2 }));
        }

        [Test]
        public void large_test_1()
        {
            double[][] costMatrix =
            {
                new[] { 0.00000000000000  , 466.560000000000   , 1399.68000000000   , 1866.24000000000   , 1399.68000000000   , 466.560000000000   , 466.560000000000   , 466.560000000000   , 466.560000000000   , 1399.68000000000  ,  1866.24000000000  ,  3265.92000000000  ,  3265.92000000000  ,  4199.04000000000  ,  3265.92000000000   , 3265.92000000000  ,  1866.24000000000  ,  1399.68000000000  },
                new[] { 1399.68000000000  ,  466.560000000000  ,  1399.68000000000  ,  3265.92000000000  ,  4199.04000000000  ,  3265.92000000000  ,  3265.92000000000  ,  1866.24000000000  ,  466.560000000000  ,  0.00000000000000 ,  466.560000000000  ,  1866.24000000000  ,  3265.92000000000  ,  5598.72000000000  ,  6065.28000000000   , 7464.96000000000  ,  6065.28000000000  ,  5598.72000000000  },
                new[] { 466.560000000000  ,  1399.68000000000  ,  1866.24000000000  ,  1399.68000000000  ,  466.560000000000  ,  0.00000000000000  , 466.560000000000   , 1399.68000000000   , 1866.24000000000   , 3265.92000000000  ,  3265.92000000000  ,  4199.04000000000  ,  3265.92000000000  ,  3265.92000000000  ,  1866.24000000000   , 1399.68000000000  ,  466.560000000000  ,  466.560000000000  },
                new[] { 1866.24000000000  ,  1399.68000000000  ,  466.560000000000  ,  0.00000000000000  , 466.560000000000   , 1399.68000000000   , 3265.92000000000   , 4199.04000000000   , 3265.92000000000   , 3265.92000000000  ,  1866.24000000000  ,  1399.68000000000  ,  466.560000000000  ,  466.560000000000  ,  466.560000000000   , 1399.68000000000  ,  1866.24000000000  ,  3265.92000000000  },
                new[] { 3265.92000000000  ,  1399.68000000000  ,  466.560000000000  ,  1399.68000000000  ,  3265.92000000000  ,  4199.04000000000  ,  6065.28000000000  ,  5598.72000000000  ,  3265.92000000000  ,  1866.24000000000 ,   466.560000000000 ,   0.00000000000000 ,  466.560000000000  ,  1866.24000000000  ,  3265.92000000000   , 5598.72000000000  ,  6065.28000000000  ,  7464.96000000000  },
                new[] { 466.560000000000  ,  1399.68000000000  ,  3265.92000000000  ,  4199.04000000000  ,  3265.92000000000  ,  1399.68000000000  ,  466.560000000000  ,  0.00000000000000  , 466.560000000000   , 1866.24000000000  ,  3265.92000000000  ,  5598.72000000000  ,  6065.28000000000  ,  7464.96000000000  ,  6065.28000000000   , 5598.72000000000  ,  3265.92000000000  ,  1866.24000000000  },
                new[] { 0.00000000000000  , 466.560000000000   , 1399.68000000000   , 1866.24000000000   , 1399.68000000000   , 466.560000000000   , 466.560000000000   , 466.560000000000   , 466.560000000000   , 1399.68000000000  ,  1866.24000000000  ,  3265.92000000000  ,  3265.92000000000  ,  4199.04000000000  ,  3265.92000000000   , 3265.92000000000  ,  1866.24000000000  ,  1399.68000000000  },
                new[] { 1399.68000000000  ,  466.560000000000  ,  1399.68000000000  ,  3265.92000000000  ,  4199.04000000000  ,  3265.92000000000  ,  3265.92000000000  ,  1866.24000000000  ,  466.560000000000  ,  0.00000000000000 ,  466.560000000000  ,  1866.24000000000  ,  3265.92000000000  ,  5598.72000000000  ,  6065.28000000000   , 7464.96000000000  ,  6065.28000000000  ,  5598.72000000000  },
                new[] { 466.560000000000  ,  1399.68000000000  ,  1866.24000000000  ,  1399.68000000000  ,  466.560000000000  ,  0.00000000000000  , 466.560000000000   , 1399.68000000000   , 1866.24000000000   , 3265.92000000000  ,  3265.92000000000  ,  4199.04000000000  ,  3265.92000000000  ,  3265.92000000000  ,  1866.24000000000   , 1399.68000000000  ,  466.560000000000  ,  466.560000000000  },
                new[] { 1866.24000000000  ,  1399.68000000000  ,  466.560000000000  ,  0.00000000000000  , 466.560000000000   , 1399.68000000000   , 3265.92000000000   , 4199.04000000000   , 3265.92000000000   , 3265.92000000000  ,  1866.24000000000  ,  1399.68000000000  ,  466.560000000000  ,  466.560000000000  ,  466.560000000000   , 1399.68000000000  ,  1866.24000000000  ,  3265.92000000000  },
                new[] { 3265.92000000000  ,  1399.68000000000  ,  466.560000000000  ,  1399.68000000000  ,  3265.92000000000  ,  4199.04000000000  ,  6065.28000000000  ,  5598.72000000000  ,  3265.92000000000  ,  1866.24000000000 ,   466.560000000000 ,   0.00000000000000 ,  466.560000000000  ,  1866.24000000000  ,  3265.92000000000   , 5598.72000000000  ,  6065.28000000000  ,  7464.96000000000  },
                new[] { 466.560000000000  ,  1399.68000000000  ,  3265.92000000000  ,  4199.04000000000  ,  3265.92000000000  ,  1399.68000000000  ,  466.560000000000  ,  0.00000000000000  , 466.560000000000   , 1866.24000000000  ,  3265.92000000000  ,  5598.72000000000  ,  6065.28000000000  ,  7464.96000000000  ,  6065.28000000000   , 5598.72000000000  ,  3265.92000000000  ,  1866.24000000000  },
                new[] { 0.00000000000000  , 466.560000000000   , 1399.68000000000   , 1866.24000000000   , 1399.68000000000   , 466.560000000000   , 466.560000000000   , 466.560000000000   , 466.560000000000   , 1399.68000000000  ,  1866.24000000000  ,  3265.92000000000  ,  3265.92000000000  ,  4199.04000000000  ,  3265.92000000000   , 3265.92000000000  ,  1866.24000000000  ,  1399.68000000000  },
                new[] { 1399.68000000000  ,  466.560000000000  ,  1399.68000000000  ,  3265.92000000000  ,  4199.04000000000  ,  3265.92000000000  ,  3265.92000000000  ,  1866.24000000000  ,  466.560000000000  ,  0.00000000000000 ,  466.560000000000  ,  1866.24000000000  ,  3265.92000000000  ,  5598.72000000000  ,  6065.28000000000   , 7464.96000000000  ,  6065.28000000000  ,  5598.72000000000  },
                new[] { 466.560000000000  ,  1399.68000000000  ,  1866.24000000000  ,  1399.68000000000  ,  466.560000000000  ,  0.00000000000000  , 466.560000000000   , 1399.68000000000   , 1866.24000000000   , 3265.92000000000  ,  3265.92000000000  ,  4199.04000000000  ,  3265.92000000000  ,  3265.92000000000  ,  1866.24000000000   , 1399.68000000000  ,  466.560000000000  ,  466.560000000000  },
                new[] { 1866.24000000000  ,  1399.68000000000  ,  466.560000000000  ,  0.00000000000000  , 466.560000000000   , 1399.68000000000   , 3265.92000000000   , 4199.04000000000   , 3265.92000000000   , 3265.92000000000  ,  1866.24000000000  ,  1399.68000000000  ,  466.560000000000  ,  466.560000000000  ,  466.560000000000   , 1399.68000000000  ,  1866.24000000000  ,  3265.92000000000  },
                new[] { 3265.92000000000  ,  1399.68000000000  ,  466.560000000000  ,  1399.68000000000  ,  3265.92000000000  ,  4199.04000000000  ,  6065.28000000000  ,  5598.72000000000  ,  3265.92000000000  ,  1866.24000000000 ,   466.560000000000 ,   0.00000000000000 ,  466.560000000000  ,  1866.24000000000  ,  3265.92000000000   , 5598.72000000000  ,  6065.28000000000  ,  7464.96000000000  },
                new[] {  466.560000000000 ,   1399.68000000000 ,   3265.92000000000 ,   4199.04000000000 ,   3265.92000000000 ,   1399.68000000000 ,   466.560000000000 ,   0.00000000000000 ,  466.560000000000  ,  1866.24000000000 ,   3265.92000000000 ,   5598.72000000000 ,   6065.28000000000 ,   7464.96000000000 ,   6065.28000000000  ,  5598.72000000000 ,   3265.92000000000 ,   1866.24000000000 },
            };

            Munkres m = new Munkres(costMatrix);

            Assert.AreEqual(18, m.NumberOfTasks);
            Assert.AreEqual(18, m.NumberOfWorkers);
            Assert.AreEqual(18 * 18, m.NumberOfVariables);

            bool success = m.Minimize();
            Assert.IsTrue(success);
            Assert.AreEqual(7931.5200000000032, m.Value);

            int[] expected = { 1, 2, 18, 14, 13, 7, 5, 10, 17, 4, 12, 8, 6, 11, 16, 15, 3, 9 };

            for (int i = 0; i < expected.Length; i++)
                Assert.AreEqual(expected[i] - 1, m.Solution[i]);
        }

        [Test]
        public void large_test_2()
        {
            double[,] costMatrix =
            {
                { 3.2659e+003, 1.8662e+003, 4.6656e+002, 4.6656e+002, 1.8662e+003, 3.2659e+003, 5.5987e+003, 6.0653e+003, 4.1990e+003, 3.2659e+003, 1.3997e+003, 4.6656e+002, 1.6339e-012, 4.6656e+002, 1.3997e+003, 3.2659e+003, 4.1990e+003, 6.0653e+003 },
                { 1.6339e-012, 4.6656e+002, 1.3997e+003, 1.8662e+003, 1.3997e+003, 4.6656e+002, 4.6656e+002, 4.6656e+002, 4.6656e+002, 1.3997e+003, 1.8662e+003, 3.2659e+003, 3.2659e+003, 4.1990e+003, 3.2659e+003, 3.2659e+003, 1.8662e+003, 1.3997e+003 },
                { 1.3997e+003, 4.6656e+002, 1.3997e+003, 3.2659e+003, 4.1990e+003, 3.2659e+003, 3.2659e+003, 1.8662e+003, 4.6656e+002, 6.5358e-012, 4.6656e+002, 1.8662e+003, 3.2659e+003, 5.5987e+003, 6.0653e+003, 7.4650e+003, 6.0653e+003, 5.5987e+003 },
                { 1.8662e+003, 1.3997e+003, 4.6656e+002, 1.6339e-012, 4.6656e+002, 1.3997e+003, 3.2659e+003, 4.1990e+003, 3.2659e+003, 3.2659e+003, 1.8662e+003, 1.3997e+003, 4.6656e+002, 4.6656e+002, 4.6656e+002, 1.3997e+003, 1.8662e+003, 3.2659e+003 },
                { 3.2659e+003, 4.1990e+003, 3.2659e+003, 1.3997e+003, 4.6656e+002, 1.3997e+003, 3.2659e+003, 5.5987e+003, 6.0653e+003, 7.4650e+003, 6.0653e+003, 5.5987e+003, 3.2659e+003, 1.8662e+003, 4.6656e+002, 6.5358e-012, 4.6656e+002, 1.8662e+003 },
                { 4.6656e+002, 4.6656e+002, 1.8662e+003, 3.2659e+003, 3.2659e+003, 1.8662e+003, 1.3997e+003, 4.6656e+002, 6.5358e-012, 4.6656e+002, 1.3997e+003, 3.2659e+003, 4.1990e+003, 6.0653e+003, 5.5987e+003, 6.0653e+003, 4.1990e+003, 3.2659e+003 },
                { 3.2659e+003, 1.8662e+003, 4.6656e+002, 4.6656e+002, 1.8662e+003, 3.2659e+003, 5.5987e+003, 6.0653e+003, 4.1990e+003, 3.2659e+003, 1.3997e+003, 4.6656e+002, 1.6339e-012, 4.6656e+002, 1.3997e+003, 3.2659e+003, 4.1990e+003, 6.0653e+003 },
                { 1.6339e-012, 4.6656e+002, 1.3997e+003, 1.8662e+003, 1.3997e+003, 4.6656e+002, 4.6656e+002, 4.6656e+002, 4.6656e+002, 1.3997e+003, 1.8662e+003, 3.2659e+003, 3.2659e+003, 4.1990e+003, 3.2659e+003, 3.2659e+003, 1.8662e+003, 1.3997e+003 },
                { 1.3997e+003, 4.6656e+002, 1.3997e+003, 3.2659e+003, 4.1990e+003, 3.2659e+003, 3.2659e+003, 1.8662e+003, 4.6656e+002, 6.5358e-012, 4.6656e+002, 1.8662e+003, 3.2659e+003, 5.5987e+003, 6.0653e+003, 7.4650e+003, 6.0653e+003, 5.5987e+003 },
                { 1.8662e+003, 1.3997e+003, 4.6656e+002, 1.6339e-012, 4.6656e+002, 1.3997e+003, 3.2659e+003, 4.1990e+003, 3.2659e+003, 3.2659e+003, 1.8662e+003, 1.3997e+003, 4.6656e+002, 4.6656e+002, 4.6656e+002, 1.3997e+003, 1.8662e+003, 3.2659e+003 },
                { 3.2659e+003, 4.1990e+003, 3.2659e+003, 1.3997e+003, 4.6656e+002, 1.3997e+003, 3.2659e+003, 5.5987e+003, 6.0653e+003, 7.4650e+003, 6.0653e+003, 5.5987e+003, 3.2659e+003, 1.8662e+003, 4.6656e+002, 6.5358e-012, 4.6656e+002, 1.8662e+003 },
                { 4.6656e+002, 4.6656e+002, 1.8662e+003, 3.2659e+003, 3.2659e+003, 1.8662e+003, 1.3997e+003, 4.6656e+002, 6.5358e-012, 4.6656e+002, 1.3997e+003, 3.2659e+003, 4.1990e+003, 6.0653e+003, 5.5987e+003, 6.0653e+003, 4.1990e+003, 3.2659e+003 },
                { 3.2659e+003, 1.8662e+003, 4.6656e+002, 4.6656e+002, 1.8662e+003, 3.2659e+003, 5.5987e+003, 6.0653e+003, 4.1990e+003, 3.2659e+003, 1.3997e+003, 4.6656e+002, 1.6339e-012, 4.6656e+002, 1.3997e+003, 3.2659e+003, 4.1990e+003, 6.0653e+003 },
                { 1.6339e-012, 4.6656e+002, 1.3997e+003, 1.8662e+003, 1.3997e+003, 4.6656e+002, 4.6656e+002, 4.6656e+002, 4.6656e+002, 1.3997e+003, 1.8662e+003, 3.2659e+003, 3.2659e+003, 4.1990e+003, 3.2659e+003, 3.2659e+003, 1.8662e+003, 1.3997e+003 },
                { 1.3997e+003, 4.6656e+002, 1.3997e+003, 3.2659e+003, 4.1990e+003, 3.2659e+003, 3.2659e+003, 1.8662e+003, 4.6656e+002, 6.5358e-012, 4.6656e+002, 1.8662e+003, 3.2659e+003, 5.5987e+003, 6.0653e+003, 7.4650e+003, 6.0653e+003, 5.5987e+003 },
                { 1.8662e+003, 1.3997e+003, 4.6656e+002, 1.6339e-012, 4.6656e+002, 1.3997e+003, 3.2659e+003, 4.1990e+003, 3.2659e+003, 3.2659e+003, 1.8662e+003, 1.3997e+003, 4.6656e+002, 4.6656e+002, 4.6656e+002, 1.3997e+003, 1.8662e+003, 3.2659e+003 },
                { 3.2659e+003, 4.1990e+003, 3.2659e+003, 1.3997e+003, 4.6656e+002, 1.3997e+003, 3.2659e+003, 5.5987e+003, 6.0653e+003, 7.4650e+003, 6.0653e+003, 5.5987e+003, 3.2659e+003, 1.8662e+003, 4.6656e+002, 6.5358e-012, 4.6656e+002, 1.8662e+003 },
                { 4.6656e+002, 4.6656e+002, 1.8662e+003, 3.2659e+003, 3.2659e+003, 1.8662e+003, 1.3997e+003, 4.6656e+002, 6.5358e-012, 4.6656e+002, 1.3997e+003, 3.2659e+003, 4.1990e+003, 6.0653e+003, 5.5987e+003, 6.0653e+003, 4.1990e+003, 3.2659e+003 }
            };

            Munkres m = new Munkres(costMatrix.ToJagged());

            Assert.AreEqual(18, m.NumberOfTasks);
            Assert.AreEqual(18, m.NumberOfWorkers);
            Assert.AreEqual(18 * 18, m.NumberOfVariables);

            bool success = m.Minimize();
            Assert.IsTrue(success);
            Assert.AreEqual(6998.4200000000255, m.Value, 1e-5);

            int[] expected = { 3, 18, 2, 4, 17, 8, 12, 6, 10, 14, 15, 9, 13, 7, 11, 5, 16, 1 };

            for (int i = 0; i < expected.Length; i++)
                Assert.AreEqual(expected[i] - 1, m.Solution[i]);
        }

        [Test]
        public void findZerosTest()
        {
            double[][] costMatrix =
            {
                new[] { 0.00000000000000  , 466.560000000000   , 1399.68000000000   , 1866.24000000000   , 1399.68000000000   , 466.560000000000   , 466.560000000000   , 466.560000000000   , 466.560000000000   , 1399.68000000000  ,  1866.24000000000  ,  3265.92000000000  ,  3265.92000000000  ,  4199.04000000000  ,  3265.92000000000   , 3265.92000000000  ,  1866.24000000000  ,  1399.68000000000  },
                new[] { 1399.68000000000  ,  466.560000000000  ,  1399.68000000000  ,  3265.92000000000  ,  4199.04000000000  ,  3265.92000000000  ,  3265.92000000000  ,  1866.24000000000  ,  466.560000000000  ,  0.00000000000000 ,  466.560000000000  ,  1866.24000000000  ,  3265.92000000000  ,  5598.72000000000  ,  6065.28000000000   , 7464.96000000000  ,  6065.28000000000  ,  5598.72000000000  },
                new[] { 466.560000000000  ,  1399.68000000000  ,  1866.24000000000  ,  1399.68000000000  ,  466.560000000000  ,  0.00000000000000  , 466.560000000000   , 1399.68000000000   , 1866.24000000000   , 3265.92000000000  ,  3265.92000000000  ,  4199.04000000000  ,  3265.92000000000  ,  3265.92000000000  ,  1866.24000000000   , 1399.68000000000  ,  466.560000000000  ,  466.560000000000  },
                new[] { 1866.24000000000  ,  1399.68000000000  ,  466.560000000000  ,  0.00000000000000  , 466.560000000000   , 1399.68000000000   , 3265.92000000000   , 4199.04000000000   , 3265.92000000000   , 3265.92000000000  ,  1866.24000000000  ,  1399.68000000000  ,  466.560000000000  ,  466.560000000000  ,  466.560000000000   , 1399.68000000000  ,  1866.24000000000  ,  3265.92000000000  },
                new[] { 3265.92000000000  ,  1399.68000000000  ,  466.560000000000  ,  1399.68000000000  ,  3265.92000000000  ,  4199.04000000000  ,  6065.28000000000  ,  5598.72000000000  ,  3265.92000000000  ,  1866.24000000000 ,   466.560000000000 ,   0.00000000000000 ,  466.560000000000  ,  1866.24000000000  ,  3265.92000000000   , 5598.72000000000  ,  6065.28000000000  ,  7464.96000000000  },
                new[] { 466.560000000000  ,  1399.68000000000  ,  3265.92000000000  ,  4199.04000000000  ,  3265.92000000000  ,  1399.68000000000  ,  466.560000000000  ,  0.00000000000000  , 466.560000000000   , 1866.24000000000  ,  3265.92000000000  ,  5598.72000000000  ,  6065.28000000000  ,  7464.96000000000  ,  6065.28000000000   , 5598.72000000000  ,  3265.92000000000  ,  1866.24000000000  },
                new[] { 0.00000000000000  , 466.560000000000   , 1399.68000000000   , 1866.24000000000   , 1399.68000000000   , 466.560000000000   , 466.560000000000   , 466.560000000000   , 466.560000000000   , 1399.68000000000  ,  1866.24000000000  ,  3265.92000000000  ,  3265.92000000000  ,  4199.04000000000  ,  3265.92000000000   , 3265.92000000000  ,  1866.24000000000  ,  1399.68000000000  },
                new[] { 1399.68000000000  ,  466.560000000000  ,  1399.68000000000  ,  3265.92000000000  ,  4199.04000000000  ,  3265.92000000000  ,  3265.92000000000  ,  1866.24000000000  ,  466.560000000000  ,  0.00000000000000 ,  466.560000000000  ,  1866.24000000000  ,  3265.92000000000  ,  5598.72000000000  ,  6065.28000000000   , 7464.96000000000  ,  6065.28000000000  ,  5598.72000000000  },
                new[] { 466.560000000000  ,  1399.68000000000  ,  1866.24000000000  ,  1399.68000000000  ,  466.560000000000  ,  0.00000000000000  , 466.560000000000   , 1399.68000000000   , 1866.24000000000   , 3265.92000000000  ,  3265.92000000000  ,  4199.04000000000  ,  3265.92000000000  ,  3265.92000000000  ,  1866.24000000000   , 1399.68000000000  ,  466.560000000000  ,  466.560000000000  },
                new[] { 1866.24000000000  ,  1399.68000000000  ,  466.560000000000  ,  0.00000000000000  , 466.560000000000   , 1399.68000000000   , 3265.92000000000   , 4199.04000000000   , 3265.92000000000   , 3265.92000000000  ,  1866.24000000000  ,  1399.68000000000  ,  466.560000000000  ,  466.560000000000  ,  466.560000000000   , 1399.68000000000  ,  1866.24000000000  ,  3265.92000000000  },
                new[] { 3265.92000000000  ,  1399.68000000000  ,  466.560000000000  ,  1399.68000000000  ,  3265.92000000000  ,  4199.04000000000  ,  6065.28000000000  ,  5598.72000000000  ,  3265.92000000000  ,  1866.24000000000 ,   466.560000000000 ,   0.00000000000000 ,  466.560000000000  ,  1866.24000000000  ,  3265.92000000000   , 5598.72000000000  ,  6065.28000000000  ,  7464.96000000000  },
                new[] { 466.560000000000  ,  1399.68000000000  ,  3265.92000000000  ,  4199.04000000000  ,  3265.92000000000  ,  1399.68000000000  ,  466.560000000000  ,  0.00000000000000  , 466.560000000000   , 1866.24000000000  ,  3265.92000000000  ,  5598.72000000000  ,  6065.28000000000  ,  7464.96000000000  ,  6065.28000000000   , 5598.72000000000  ,  3265.92000000000  ,  1866.24000000000  },
                new[] { 0.00000000000000  , 466.560000000000   , 1399.68000000000   , 1866.24000000000   , 1399.68000000000   , 466.560000000000   , 466.560000000000   , 466.560000000000   , 466.560000000000   , 1399.68000000000  ,  1866.24000000000  ,  3265.92000000000  ,  3265.92000000000  ,  4199.04000000000  ,  3265.92000000000   , 3265.92000000000  ,  1866.24000000000  ,  1399.68000000000  },
                new[] { 1399.68000000000  ,  466.560000000000  ,  1399.68000000000  ,  3265.92000000000  ,  4199.04000000000  ,  3265.92000000000  ,  3265.92000000000  ,  1866.24000000000  ,  466.560000000000  ,  0.00000000000000 ,  466.560000000000  ,  1866.24000000000  ,  3265.92000000000  ,  5598.72000000000  ,  6065.28000000000   , 7464.96000000000  ,  6065.28000000000  ,  5598.72000000000  },
                new[] { 466.560000000000  ,  1399.68000000000  ,  1866.24000000000  ,  1399.68000000000  ,  466.560000000000  ,  0.00000000000000  , 466.560000000000   , 1399.68000000000   , 1866.24000000000   , 3265.92000000000  ,  3265.92000000000  ,  4199.04000000000  ,  3265.92000000000  ,  3265.92000000000  ,  1866.24000000000   , 1399.68000000000  ,  466.560000000000  ,  466.560000000000  },
                new[] { 1866.24000000000  ,  1399.68000000000  ,  466.560000000000  ,  0.00000000000000  , 466.560000000000   , 1399.68000000000   , 3265.92000000000   , 4199.04000000000   , 3265.92000000000   , 3265.92000000000  ,  1866.24000000000  ,  1399.68000000000  ,  466.560000000000  ,  466.560000000000  ,  466.560000000000   , 1399.68000000000  ,  1866.24000000000  ,  3265.92000000000  },
                new[] { 3265.92000000000  ,  1399.68000000000  ,  466.560000000000  ,  1399.68000000000  ,  3265.92000000000  ,  4199.04000000000  ,  6065.28000000000  ,  5598.72000000000  ,  3265.92000000000  ,  1866.24000000000 ,   466.560000000000 ,   0.00000000000000 ,  466.560000000000  ,  1866.24000000000  ,  3265.92000000000   , 5598.72000000000  ,  6065.28000000000  ,  7464.96000000000  },
                new[] {  466.560000000000 ,   1399.68000000000 ,   3265.92000000000 ,   4199.04000000000 ,   3265.92000000000 ,   1399.68000000000 ,   466.560000000000 ,   0.00000000000000 ,  466.560000000000  ,  1866.24000000000 ,   3265.92000000000 ,   5598.72000000000 ,   6065.28000000000 ,   7464.96000000000 ,   6065.28000000000  ,  5598.72000000000 ,   3265.92000000000 ,   1866.24000000000 },
            };

            var minRow = Matrix.Min(costMatrix, dimension: 1);
            var minCol = Matrix.Min(costMatrix.Subtract(minRow, dimension: 0), dimension: 0);
            double[][] min;
            bool[][] M = Munkres.findZeros(costMatrix, minRow, minCol, out min);


            double[,] expectedMin =
            {
                { 0,   466.560000000000,    466.560000000000,    0,   466.560000000000,    0,   466.560000000000,    0,   466.560000000000,    0,   466.560000000000,    0,   466.560000000000,    466.560000000000,    466.560000000000,    1399.68000000000,    466.560000000000,    466.560000000000 },
                { 0,   466.560000000000,    466.560000000000,    0,   466.560000000000,    0,   466.560000000000,    0,   466.560000000000,    0,   466.560000000000,    0,   466.560000000000,    466.560000000000,    466.560000000000,    1399.68000000000,    466.560000000000,    466.560000000000 },
                { 0,   466.560000000000,    466.560000000000,    0,   466.560000000000,    0,   466.560000000000,    0,   466.560000000000,    0,   466.560000000000,    0,   466.560000000000,    466.560000000000,    466.560000000000,    1399.68000000000,    466.560000000000,    466.560000000000 },
                { 0,   466.560000000000,    466.560000000000,    0,   466.560000000000,    0,   466.560000000000,    0,   466.560000000000,    0,   466.560000000000,    0,   466.560000000000,    466.560000000000,    466.560000000000,    1399.68000000000,    466.560000000000,    466.560000000000 },
                { 0,   466.560000000000,    466.560000000000,    0,   466.560000000000,    0,   466.560000000000,    0,   466.560000000000,    0,   466.560000000000,    0,   466.560000000000,    466.560000000000,    466.560000000000,    1399.68000000000,    466.560000000000,    466.560000000000 },
                { 0,   466.560000000000,    466.560000000000,    0,   466.560000000000,    0,   466.560000000000,    0,   466.560000000000,    0,   466.560000000000,    0,   466.560000000000,    466.560000000000,    466.560000000000,    1399.68000000000,    466.560000000000,    466.560000000000 },
                { 0,   466.560000000000,    466.560000000000,    0,   466.560000000000,    0,   466.560000000000,    0,   466.560000000000,    0,   466.560000000000,    0,   466.560000000000,    466.560000000000,    466.560000000000,    1399.68000000000,    466.560000000000,    466.560000000000 },
                { 0,   466.560000000000,    466.560000000000,    0,   466.560000000000,    0,   466.560000000000,    0,   466.560000000000,    0,   466.560000000000,    0,   466.560000000000,    466.560000000000,    466.560000000000,    1399.68000000000,    466.560000000000,    466.560000000000 },
                { 0,   466.560000000000,    466.560000000000,    0,   466.560000000000,    0,   466.560000000000,    0,   466.560000000000,    0,   466.560000000000,    0,   466.560000000000,    466.560000000000,    466.560000000000,    1399.68000000000,    466.560000000000,    466.560000000000 },
                { 0,   466.560000000000,    466.560000000000,    0,   466.560000000000,    0,   466.560000000000,    0,   466.560000000000,    0,   466.560000000000,    0,   466.560000000000,    466.560000000000,    466.560000000000,    1399.68000000000,    466.560000000000,    466.560000000000 },
                { 0,   466.560000000000,    466.560000000000,    0,   466.560000000000,    0,   466.560000000000,    0,   466.560000000000,    0,   466.560000000000,    0,   466.560000000000,    466.560000000000,    466.560000000000,    1399.68000000000,    466.560000000000,    466.560000000000 },
                { 0,   466.560000000000,    466.560000000000,    0,   466.560000000000,    0,   466.560000000000,    0,   466.560000000000,    0,   466.560000000000,    0,   466.560000000000,    466.560000000000,    466.560000000000,    1399.68000000000,    466.560000000000,    466.560000000000 },
                { 0,   466.560000000000,    466.560000000000,    0,   466.560000000000,    0,   466.560000000000,    0,   466.560000000000,    0,   466.560000000000,    0,   466.560000000000,    466.560000000000,    466.560000000000,    1399.68000000000,    466.560000000000,    466.560000000000 },
                { 0,   466.560000000000,    466.560000000000,    0,   466.560000000000,    0,   466.560000000000,    0,   466.560000000000,    0,   466.560000000000,    0,   466.560000000000,    466.560000000000,    466.560000000000,    1399.68000000000,    466.560000000000,    466.560000000000 },
                { 0,   466.560000000000,    466.560000000000,    0,   466.560000000000,    0,   466.560000000000,    0,   466.560000000000,    0,   466.560000000000,    0,   466.560000000000,    466.560000000000,    466.560000000000,    1399.68000000000,    466.560000000000,    466.560000000000 },
                { 0,   466.560000000000,    466.560000000000,    0,   466.560000000000,    0,   466.560000000000,    0,   466.560000000000,    0,   466.560000000000,    0,   466.560000000000,    466.560000000000,    466.560000000000,    1399.68000000000,    466.560000000000,    466.560000000000 },
                { 0,   466.560000000000,    466.560000000000,    0,   466.560000000000,    0,   466.560000000000,    0,   466.560000000000,    0,   466.560000000000,    0,   466.560000000000,    466.560000000000,    466.560000000000,    1399.68000000000,    466.560000000000,    466.560000000000 },
                { 0,   466.560000000000,    466.560000000000,    0,   466.560000000000,    0,   466.560000000000,    0,   466.560000000000,    0,   466.560000000000,    0,   466.560000000000,    466.560000000000,    466.560000000000,    1399.68000000000,    466.560000000000,    466.560000000000 },
            };

            Assert.AreEqual(min[2][6], expectedMin[2, 6]);
            Assert.IsTrue(min.IsEqual(expectedMin));

            int[,] expectedM =
            {
                { 1, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
                { 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0 },
                { 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1 },
                { 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0 },
                { 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0 },
                { 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
                { 1, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
                { 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0 },
                { 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1 },
                { 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0 },
                { 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0 },
                { 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
                { 1, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
                { 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0 },
                { 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1 },
                { 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0 },
                { 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0 },
                { 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
            };

            Assert.AreEqual(M[2][6] ? 1 : 0, expectedM[2, 6]);
            Assert.IsTrue(M.IsEqual(expectedM));
        }


        [Test]
        public void gh_684()
        {
            // https://github.com/accord-net/framework/issues/684
            Accord.Math.Random.Generator.Seed = 0;

            double[][] costMatrix = new double[][]
            {
                new double[] { 0, 698914969, 689797696, 642369025, 689587600, 691532209, 694217104, 702674064, 651729841, 680479396, 702038016, 653671489, 698703489, 668636164, 643484689, 653109136, 701720100, 631969321, 680896836, 638926729, 624400144, 647702500, 635443264, 692058249, 678550401, 649638144, 685444761, 652138369, 693532225, 695218689, 656435641, 702621049, 635090401, 668532736 },
                new double[] { 695565269.897959, 4023.18367346939, 12005.8979591837, 1057959.18367347, 12898.4693877551, 5863.18367346939, 653.897959183674, 18071.0408163265, 713300.897959184, 82697.3265306122, 14988.7551020408, 650557.469387755, 3531.75510204082, 265813.897959184, 1013186.04081633, 668423.040816327, 13555.612244898, 1524166.6122449, 78160.1836734694, 1202468.89795918, 1919808.18367347, 852984.183673469, 1358556.75510204, 4431.75510204082, 105346.612244898, 784236.755102041, 37083.7551020408, 699851.755102041, 1487.75510204082, 43.1836734693879, 566363.755102041, 17803.1836734694, 1374923.75510204, 267880.183673469 },
                new double[] { 652173314.836565, 808768.889196676, 527534.626038781, 37127.2049861496, 521740.099722992, 576560.468144044, 656611.67867036, 941512.731301939, 75.4155124653748, 300650.20498615, 918369.152354571, 859.415512465371, 801590.362880886, 102602.20498615, 29133.0997229917, 335.46814404432, 906905.362880886, 158949.099722992, 309487.257617728, 67956.2576177286, 302152.731301939, 7688.52077562328, 108691.67867036, 591846.783933518, 261443.836565097, 2468.52077562327, 413855.20498615, 0.468144044321395, 635712.468144044, 687764.67867036, 6941.52077562326, 939573.099722992, 113356.257617729, 101324.941828255 },
                new double[] { 0, 698914969, 689797696, 642369025, 689587600, 691532209, 694217104, 702674064, 651729841, 680479396, 702038016, 653671489, 698703489, 668636164, 643484689, 653109136, 701720100, 631969321, 680896836, 638926729, 624400144, 647702500, 635443264, 692058249, 678550401, 649638144, 685444761, 652138369, 693532225, 695218689, 656435641, 702621049, 635090401, 668532736 },
                new double[] { 695565269.897959, 4023.18367346939, 12005.8979591837, 1057959.18367347, 12898.4693877551, 5863.18367346939, 653.897959183674, 18071.0408163265, 713300.897959184, 82697.3265306122, 14988.7551020408, 650557.469387755, 3531.75510204082, 265813.897959184, 1013186.04081633, 668423.040816327, 13555.612244898, 1524166.6122449, 78160.1836734694, 1202468.89795918, 1919808.18367347, 852984.183673469, 1358556.75510204, 4431.75510204082, 105346.612244898, 784236.755102041, 37083.7551020408, 699851.755102041, 1487.75510204082, 43.1836734693879, 566363.755102041, 17803.1836734694, 1374923.75510204, 267880.183673469 },
                new double[] { 652173314.836565, 808768.889196676, 527534.626038781, 37127.2049861496, 521740.099722992, 576560.468144044, 656611.67867036, 941512.731301939, 75.4155124653748, 300650.20498615, 918369.152354571, 859.415512465371, 801590.362880886, 102602.20498615, 29133.0997229917, 335.46814404432, 906905.362880886, 158949.099722992, 309487.257617728, 67956.2576177286, 302152.731301939, 7688.52077562328, 108691.67867036, 591846.783933518, 261443.836565097, 2468.52077562327, 413855.20498615, 0.468144044321395, 635712.468144044, 687764.67867036, 6941.52077562326, 939573.099722992, 113356.257617729, 101324.941828255 },
                new double[] { 0, 698914969, 689797696, 642369025, 689587600, 691532209, 694217104, 702674064, 651729841, 680479396, 702038016, 653671489, 698703489, 668636164, 643484689, 653109136, 701720100, 631969321, 680896836, 638926729, 624400144, 647702500, 635443264, 692058249, 678550401, 649638144, 685444761, 652138369, 693532225, 695218689, 656435641, 702621049, 635090401, 668532736 },
                new double[] { 695565269.897959, 4023.18367346939, 12005.8979591837, 1057959.18367347, 12898.4693877551, 5863.18367346939, 653.897959183674, 18071.0408163265, 713300.897959184, 82697.3265306122, 14988.7551020408, 650557.469387755, 3531.75510204082, 265813.897959184, 1013186.04081633, 668423.040816327, 13555.612244898, 1524166.6122449, 78160.1836734694, 1202468.89795918, 1919808.18367347, 852984.183673469, 1358556.75510204, 4431.75510204082, 105346.612244898, 784236.755102041, 37083.7551020408, 699851.755102041, 1487.75510204082, 43.1836734693879, 566363.755102041, 17803.1836734694, 1374923.75510204, 267880.183673469 },
                new double[] { 652173314.836565, 808768.889196676, 527534.626038781, 37127.2049861496, 521740.099722992, 576560.468144044, 656611.67867036, 941512.731301939, 75.4155124653748, 300650.20498615, 918369.152354571, 859.415512465371, 801590.362880886, 102602.20498615, 29133.0997229917, 335.46814404432, 906905.362880886, 158949.099722992, 309487.257617728, 67956.2576177286, 302152.731301939, 7688.52077562328, 108691.67867036, 591846.783933518, 261443.836565097, 2468.52077562327, 413855.20498615, 0.468144044321395, 635712.468144044, 687764.67867036, 6941.52077562326, 939573.099722992, 113356.257617729, 101324.941828255 },
                new double[] { 0, 698914969, 689797696, 642369025, 689587600, 691532209, 694217104, 702674064, 651729841, 680479396, 702038016, 653671489, 698703489, 668636164, 643484689, 653109136, 701720100, 631969321, 680896836, 638926729, 624400144, 647702500, 635443264, 692058249, 678550401, 649638144, 685444761, 652138369, 693532225, 695218689, 656435641, 702621049, 635090401, 668532736 },
                new double[] { 695565269.897959, 4023.18367346939, 12005.8979591837, 1057959.18367347, 12898.4693877551, 5863.18367346939, 653.897959183674, 18071.0408163265, 713300.897959184, 82697.3265306122, 14988.7551020408, 650557.469387755, 3531.75510204082, 265813.897959184, 1013186.04081633, 668423.040816327, 13555.612244898, 1524166.6122449, 78160.1836734694, 1202468.89795918, 1919808.18367347, 852984.183673469, 1358556.75510204, 4431.75510204082, 105346.612244898, 784236.755102041, 37083.7551020408, 699851.755102041, 1487.75510204082, 43.1836734693879, 566363.755102041, 17803.1836734694, 1374923.75510204, 267880.183673469 },
                new double[] { 652173314.836565, 808768.889196676, 527534.626038781, 37127.2049861496, 521740.099722992, 576560.468144044, 656611.67867036, 941512.731301939, 75.4155124653748, 300650.20498615, 918369.152354571, 859.415512465371, 801590.362880886, 102602.20498615, 29133.0997229917, 335.46814404432, 906905.362880886, 158949.099722992, 309487.257617728, 67956.2576177286, 302152.731301939, 7688.52077562328, 108691.67867036, 591846.783933518, 261443.836565097, 2468.52077562327, 413855.20498615, 0.468144044321395, 635712.468144044, 687764.67867036, 6941.52077562326, 939573.099722992, 113356.257617729, 101324.941828255 },
                new double[] { 0, 698914969, 689797696, 642369025, 689587600, 691532209, 694217104, 702674064, 651729841, 680479396, 702038016, 653671489, 698703489, 668636164, 643484689, 653109136, 701720100, 631969321, 680896836, 638926729, 624400144, 647702500, 635443264, 692058249, 678550401, 649638144, 685444761, 652138369, 693532225, 695218689, 656435641, 702621049, 635090401, 668532736 },
                new double[] { 695565269.897959, 4023.18367346939, 12005.8979591837, 1057959.18367347, 12898.4693877551, 5863.18367346939, 653.897959183674, 18071.0408163265, 713300.897959184, 82697.3265306122, 14988.7551020408, 650557.469387755, 3531.75510204082, 265813.897959184, 1013186.04081633, 668423.040816327, 13555.612244898, 1524166.6122449, 78160.1836734694, 1202468.89795918, 1919808.18367347, 852984.183673469, 1358556.75510204, 4431.75510204082, 105346.612244898, 784236.755102041, 37083.7551020408, 699851.755102041, 1487.75510204082, 43.1836734693879, 566363.755102041, 17803.1836734694, 1374923.75510204, 267880.183673469 },
                new double[] { 652173314.836565, 808768.889196676, 527534.626038781, 37127.2049861496, 521740.099722992, 576560.468144044, 656611.67867036, 941512.731301939, 75.4155124653748, 300650.20498615, 918369.152354571, 859.415512465371, 801590.362880886, 102602.20498615, 29133.0997229917, 335.46814404432, 906905.362880886, 158949.099722992, 309487.257617728, 67956.2576177286, 302152.731301939, 7688.52077562328, 108691.67867036, 591846.783933518, 261443.836565097, 2468.52077562327, 413855.20498615, 0.468144044321395, 635712.468144044, 687764.67867036, 6941.52077562326, 939573.099722992, 113356.257617729, 101324.941828255 },
                new double[] { 0, 698914969, 689797696, 642369025, 689587600, 691532209, 694217104, 702674064, 651729841, 680479396, 702038016, 653671489, 698703489, 668636164, 643484689, 653109136, 701720100, 631969321, 680896836, 638926729, 624400144, 647702500, 635443264, 692058249, 678550401, 649638144, 685444761, 652138369, 693532225, 695218689, 656435641, 702621049, 635090401, 668532736 },
                new double[] { 695565269.897959, 4023.18367346939, 12005.8979591837, 1057959.18367347, 12898.4693877551, 5863.18367346939, 653.897959183674, 18071.0408163265, 713300.897959184, 82697.3265306122, 14988.7551020408, 650557.469387755, 3531.75510204082, 265813.897959184, 1013186.04081633, 668423.040816327, 13555.612244898, 1524166.6122449, 78160.1836734694, 1202468.89795918, 1919808.18367347, 852984.183673469, 1358556.75510204, 4431.75510204082, 105346.612244898, 784236.755102041, 37083.7551020408, 699851.755102041, 1487.75510204082, 43.1836734693879, 566363.755102041, 17803.1836734694, 1374923.75510204, 267880.183673469 },
                new double[] { 652173314.836565, 808768.889196676, 527534.626038781, 37127.2049861496, 521740.099722992, 576560.468144044, 656611.67867036, 941512.731301939, 75.4155124653748, 300650.20498615, 918369.152354571, 859.415512465371, 801590.362880886, 102602.20498615, 29133.0997229917, 335.46814404432, 906905.362880886, 158949.099722992, 309487.257617728, 67956.2576177286, 302152.731301939, 7688.52077562328, 108691.67867036, 591846.783933518, 261443.836565097, 2468.52077562327, 413855.20498615, 0.468144044321395, 635712.468144044, 687764.67867036, 6941.52077562326, 939573.099722992, 113356.257617729, 101324.941828255 },
                new double[] { 0, 698914969, 689797696, 642369025, 689587600, 691532209, 694217104, 702674064, 651729841, 680479396, 702038016, 653671489, 698703489, 668636164, 643484689, 653109136, 701720100, 631969321, 680896836, 638926729, 624400144, 647702500, 635443264, 692058249, 678550401, 649638144, 685444761, 652138369, 693532225, 695218689, 656435641, 702621049, 635090401, 668532736 },
                new double[] { 695565269.897959, 4023.18367346939, 12005.8979591837, 1057959.18367347, 12898.4693877551, 5863.18367346939, 653.897959183674, 18071.0408163265, 713300.897959184, 82697.3265306122, 14988.7551020408, 650557.469387755, 3531.75510204082, 265813.897959184, 1013186.04081633, 668423.040816327, 13555.612244898, 1524166.6122449, 78160.1836734694, 1202468.89795918, 1919808.18367347, 852984.183673469, 1358556.75510204, 4431.75510204082, 105346.612244898, 784236.755102041, 37083.7551020408, 699851.755102041, 1487.75510204082, 43.1836734693879, 566363.755102041, 17803.1836734694, 1374923.75510204, 267880.183673469 },
                new double[] { 652173314.836565, 808768.889196676, 527534.626038781, 37127.2049861496, 521740.099722992, 576560.468144044, 656611.67867036, 941512.731301939, 75.4155124653748, 300650.20498615, 918369.152354571, 859.415512465371, 801590.362880886, 102602.20498615, 29133.0997229917, 335.46814404432, 906905.362880886, 158949.099722992, 309487.257617728, 67956.2576177286, 302152.731301939, 7688.52077562328, 108691.67867036, 591846.783933518, 261443.836565097, 2468.52077562327, 413855.20498615, 0.468144044321395, 635712.468144044, 687764.67867036, 6941.52077562326, 939573.099722992, 113356.257617729, 101324.941828255 },
                new double[] { 0, 698914969, 689797696, 642369025, 689587600, 691532209, 694217104, 702674064, 651729841, 680479396, 702038016, 653671489, 698703489, 668636164, 643484689, 653109136, 701720100, 631969321, 680896836, 638926729, 624400144, 647702500, 635443264, 692058249, 678550401, 649638144, 685444761, 652138369, 693532225, 695218689, 656435641, 702621049, 635090401, 668532736 },
                new double[] { 695565269.897959, 4023.18367346939, 12005.8979591837, 1057959.18367347, 12898.4693877551, 5863.18367346939, 653.897959183674, 18071.0408163265, 713300.897959184, 82697.3265306122, 14988.7551020408, 650557.469387755, 3531.75510204082, 265813.897959184, 1013186.04081633, 668423.040816327, 13555.612244898, 1524166.6122449, 78160.1836734694, 1202468.89795918, 1919808.18367347, 852984.183673469, 1358556.75510204, 4431.75510204082, 105346.612244898, 784236.755102041, 37083.7551020408, 699851.755102041, 1487.75510204082, 43.1836734693879, 566363.755102041, 17803.1836734694, 1374923.75510204, 267880.183673469 },
                new double[] { 652173314.836565, 808768.889196676, 527534.626038781, 37127.2049861496, 521740.099722992, 576560.468144044, 656611.67867036, 941512.731301939, 75.4155124653748, 300650.20498615, 918369.152354571, 859.415512465371, 801590.362880886, 102602.20498615, 29133.0997229917, 335.46814404432, 906905.362880886, 158949.099722992, 309487.257617728, 67956.2576177286, 302152.731301939, 7688.52077562328, 108691.67867036, 591846.783933518, 261443.836565097, 2468.52077562327, 413855.20498615, 0.468144044321395, 635712.468144044, 687764.67867036, 6941.52077562326, 939573.099722992, 113356.257617729, 101324.941828255 },
                new double[] { 0, 698914969, 689797696, 642369025, 689587600, 691532209, 694217104, 702674064, 651729841, 680479396, 702038016, 653671489, 698703489, 668636164, 643484689, 653109136, 701720100, 631969321, 680896836, 638926729, 624400144, 647702500, 635443264, 692058249, 678550401, 649638144, 685444761, 652138369, 693532225, 695218689, 656435641, 702621049, 635090401, 668532736 },
                new double[] { 695565269.897959, 4023.18367346939, 12005.8979591837, 1057959.18367347, 12898.4693877551, 5863.18367346939, 653.897959183674, 18071.0408163265, 713300.897959184, 82697.3265306122, 14988.7551020408, 650557.469387755, 3531.75510204082, 265813.897959184, 1013186.04081633, 668423.040816327, 13555.612244898, 1524166.6122449, 78160.1836734694, 1202468.89795918, 1919808.18367347, 852984.183673469, 1358556.75510204, 4431.75510204082, 105346.612244898, 784236.755102041, 37083.7551020408, 699851.755102041, 1487.75510204082, 43.1836734693879, 566363.755102041, 17803.1836734694, 1374923.75510204, 267880.183673469 },
                new double[] { 652173314.836565, 808768.889196676, 527534.626038781, 37127.2049861496, 521740.099722992, 576560.468144044, 656611.67867036, 941512.731301939, 75.4155124653748, 300650.20498615, 918369.152354571, 859.415512465371, 801590.362880886, 102602.20498615, 29133.0997229917, 335.46814404432, 906905.362880886, 158949.099722992, 309487.257617728, 67956.2576177286, 302152.731301939, 7688.52077562328, 108691.67867036, 591846.783933518, 261443.836565097, 2468.52077562327, 413855.20498615, 0.468144044321395, 635712.468144044, 687764.67867036, 6941.52077562326, 939573.099722992, 113356.257617729, 101324.941828255 },
                new double[] { 0, 698914969, 689797696, 642369025, 689587600, 691532209, 694217104, 702674064, 651729841, 680479396, 702038016, 653671489, 698703489, 668636164, 643484689, 653109136, 701720100, 631969321, 680896836, 638926729, 624400144, 647702500, 635443264, 692058249, 678550401, 649638144, 685444761, 652138369, 693532225, 695218689, 656435641, 702621049, 635090401, 668532736 },
                new double[] { 695565269.897959, 4023.18367346939, 12005.8979591837, 1057959.18367347, 12898.4693877551, 5863.18367346939, 653.897959183674, 18071.0408163265, 713300.897959184, 82697.3265306122, 14988.7551020408, 650557.469387755, 3531.75510204082, 265813.897959184, 1013186.04081633, 668423.040816327, 13555.612244898, 1524166.6122449, 78160.1836734694, 1202468.89795918, 1919808.18367347, 852984.183673469, 1358556.75510204, 4431.75510204082, 105346.612244898, 784236.755102041, 37083.7551020408, 699851.755102041, 1487.75510204082, 43.1836734693879, 566363.755102041, 17803.1836734694, 1374923.75510204, 267880.183673469 },
                new double[] { 652173314.836565, 808768.889196676, 527534.626038781, 37127.2049861496, 521740.099722992, 576560.468144044, 656611.67867036, 941512.731301939, 75.4155124653748, 300650.20498615, 918369.152354571, 859.415512465371, 801590.362880886, 102602.20498615, 29133.0997229917, 335.46814404432, 906905.362880886, 158949.099722992, 309487.257617728, 67956.2576177286, 302152.731301939, 7688.52077562328, 108691.67867036, 591846.783933518, 261443.836565097, 2468.52077562327, 413855.20498615, 0.468144044321395, 635712.468144044, 687764.67867036, 6941.52077562326, 939573.099722992, 113356.257617729, 101324.941828255 },
                new double[] { 0, 698914969, 689797696, 642369025, 689587600, 691532209, 694217104, 702674064, 651729841, 680479396, 702038016, 653671489, 698703489, 668636164, 643484689, 653109136, 701720100, 631969321, 680896836, 638926729, 624400144, 647702500, 635443264, 692058249, 678550401, 649638144, 685444761, 652138369, 693532225, 695218689, 656435641, 702621049, 635090401, 668532736 },
                new double[] { 695565269.897959, 4023.18367346939, 12005.8979591837, 1057959.18367347, 12898.4693877551, 5863.18367346939, 653.897959183674, 18071.0408163265, 713300.897959184, 82697.3265306122, 14988.7551020408, 650557.469387755, 3531.75510204082, 265813.897959184, 1013186.04081633, 668423.040816327, 13555.612244898, 1524166.6122449, 78160.1836734694, 1202468.89795918, 1919808.18367347, 852984.183673469, 1358556.75510204, 4431.75510204082, 105346.612244898, 784236.755102041, 37083.7551020408, 699851.755102041, 1487.75510204082, 43.1836734693879, 566363.755102041, 17803.1836734694, 1374923.75510204, 267880.183673469 },
                new double[] { 652173314.836565, 808768.889196676, 527534.626038781, 37127.2049861496, 521740.099722992, 576560.468144044, 656611.67867036, 941512.731301939, 75.4155124653748, 300650.20498615, 918369.152354571, 859.415512465371, 801590.362880886, 102602.20498615, 29133.0997229917, 335.46814404432, 906905.362880886, 158949.099722992, 309487.257617728, 67956.2576177286, 302152.731301939, 7688.52077562328, 108691.67867036, 591846.783933518, 261443.836565097, 2468.52077562327, 413855.20498615, 0.468144044321395, 635712.468144044, 687764.67867036, 6941.52077562326, 939573.099722992, 113356.257617729, 101324.941828255 },
                new double[] { 0, 698914969, 689797696, 642369025, 689587600, 691532209, 694217104, 702674064, 651729841, 680479396, 702038016, 653671489, 698703489, 668636164, 643484689, 653109136, 701720100, 631969321, 680896836, 638926729, 624400144, 647702500, 635443264, 692058249, 678550401, 649638144, 685444761, 652138369, 693532225, 695218689, 656435641, 702621049, 635090401, 668532736 }
            };

            var munkres = new Munkres(costMatrix);
            munkres.Tolerance = 1e-5;

            bool success = munkres.Minimize();

            double[] solution = munkres.Solution;
            double[] expected = { 0, 1, 24, 20, 31, 4, 17, 29, 11, 32, 5, 13, 22, 6, 9, 19, 7, 15, 3, 23, 2, 14, 10, 33, 21, 12, 26, 25, 16, 18, 8, 28, 30, 27 };

            Assert.AreEqual(expected, solution);
        }
    }
}
